/*
 * @Author: 0x9DEFA478
 * @Date: 2025-07-09 21:40:04
 * @LastEditTime: 2025-09-13 16:38:54
 * @LastEditors: 0x9DEFA478
 * @Description: 
 * 
 */
#include "./H_Tree_AVL.h"




static inline int ReplaceChildNode(H_TreeNode* Parent,H_TreeNode* Node,H_TreeNode* ChildNode){

  if(Parent->Left==Node){// Left
    Parent->Left=ChildNode;
    return 1;
  }
  // Right
  Parent->Right=ChildNode;
  
  return 0;
}

static int RemoveNode_LR(H_TreeNode_AVL** Tree,H_TreeNode** Node){
  H_TreeNode* tNode;
  H_TreeNode* lNode;
  H_TreeNode* node;

  tNode=*Node;
  lNode=tNode->Left;

  node=lNode;
  while(node->Right!=NULL){
    node=node->Right;
  }

  if(node==lNode){//左子节点就已经没有右节点的情况
    H_TreeNode* Parent;
    H_TreeNode* Right;

    Parent=tNode->Parent;
    if(Parent==NULL){
      *Tree=H_TreeNode_To_H_TreeNode_AVL(node);
    }else{
      ReplaceChildNode(Parent,tNode,node);
    }
    H_TreeNode_To_H_TreeNode_AVL(node)->Factor=H_TreeNode_To_H_TreeNode_AVL(tNode)->Factor;//继承逻辑上被去除节点的因子
    node->Parent=Parent;
    Right=tNode->Right;//right肯定存在
    node->Right=Right;
    Right->Parent=node;
    *Node=node;
    return 1;//空出的节点有左子节点替代, 因子使用被去除节点的因子 树高度上相当于左子树变矮
  }else{
    H_TreeNode* Parent;
    H_TreeNode* ChildNode;

    //移除前驱node
    {
      Parent=node->Parent;
      ChildNode=node->Left;
      if(ChildNode!=NULL){
        ChildNode->Parent=Parent;
      }
      Parent->Right=ChildNode;
      *Node=Parent;//结构上被去除节点的父节点
    }

    //前驱节点node移动 到 逻辑上被去除节点 的位置
    *H_TreeNode_To_H_TreeNode_AVL(node)=*H_TreeNode_To_H_TreeNode_AVL(tNode);
    Parent=tNode->Parent;
    if(Parent==NULL){
      *Tree=H_TreeNode_To_H_TreeNode_AVL(node);
    }else{
      ReplaceChildNode(Parent,tNode,node);
    }
    ChildNode=node->Left;
    ChildNode->Parent=node;
    ChildNode=node->Right;
    ChildNode->Parent=node;

    return 0;//从结构看是前驱节点被去除了 前驱节点是右节点 相当于右子树变矮
  }

}


static inline H_TreeNode* adjustNode_L(H_TreeNode_AVL** Tree,H_TreeNode* Node,int* LevelDecrease){
  H_TreeNode* Parent;
  H_TreeNode* L;
  H_TreeNode* LR;
  int L_Factor;

  L=Node->Left;//此时L肯定存在
  L_Factor=H_TreeNode_To_H_TreeNode_AVL(L)->Factor;
  if(L_Factor>0){//LR最高
    int LR_Fact;
    H_TreeNode* LRL;
    H_TreeNode* LRR;
    //转换为LL最高

    /**  LR_Factor=0
     *
     *         Node                             LR
     *        /   \                            /  \ 
     *       /     \                          /    \ 
     *      /       \         ------>        /      \ 
     *     L                                L       Node
     *    / \                              / \      /  \ 
     *   /   \                            /   \    /    \ 
     *        LR                              LRL LRR
     *       /  \ 
     *     LRL  LRR
     * 
     */

    /**  LR_Factor=-1
     *
     *         Node                             LR
     *        /   \                            /  \ 
     *       /     \                          /    \ 
     *      /       \         ------>        /      \ 
     *     L                                L       Node
     *    / \                              / \         \ 
     *   /   \                            /   \         \ 
     *        LR                              LRL
     *       /
     *     LRL
     */

    /**  LR_Factor=1
     *
     *         Node                             LR
     *        /   \                            /  \ 
     *       /     \                          /    \ 
     *      /       \         ------>        /      \ 
     *     L                                L       Node
     *    / \                              /        /  \ 
     *   /   \                            /        /    \ 
     *        LR                                  LRR
     *          \  
     *          LRR
     */

    LR=L->Right;//此时LR肯定存在
    LRL=LR->Left;
    LRR=LR->Right;
    Parent=Node->Parent;

    Node->Parent=LR;
    L->Parent=LR;
    LR->Parent=Parent;
    if(LRL!=NULL){
      LRL->Parent=L;
    }
    if(LRR!=NULL){
      LRR->Parent=Node;
    }

    if(Parent==NULL){
      *Tree=H_TreeNode_To_H_TreeNode_AVL(LR);
    }else{
      ReplaceChildNode(Parent,Node,LR);
    }
    Node->Left=LRR;
    L->Right=LRL;
    LR->Left=L;
    LR->Right=Node;

    //因子更正
    LR_Fact=H_TreeNode_To_H_TreeNode_AVL(LR)->Factor;
    if(LR_Fact==(-1)){
      H_TreeNode_To_H_TreeNode_AVL(Node)->Factor=1;
    }else{
      H_TreeNode_To_H_TreeNode_AVL(Node)->Factor=0;
    }
    if(LR_Fact==1){
      H_TreeNode_To_H_TreeNode_AVL(L)->Factor=-1;
    }else{
      H_TreeNode_To_H_TreeNode_AVL(L)->Factor=0;
    }
    H_TreeNode_To_H_TreeNode_AVL(LR)->Factor=0;

    *LevelDecrease=1;
    Node=LR;
  }else{
    //LL最高
    
    /**  L_Factor=-1
     *
     *         Node                             L
     *        /   \                            / \ 
     *       /     \                          /   \ 
     *      /       \         ------>        /     \ 
     *     L                                LL     Node
     *    / \                              /  \    /  \ 
     *   /   \                            /    \  /    \ 
     *  LL    LR                                 LR
     * /  \ 
     */
    
    /**  L_Factor=0
     *
     *         Node                             L
     *        /   \                            / \ 
     *       /     \                          /   \ 
     *      /       \         ------>        /     \ 
     *     L                                LL     Node
     *    / \                              /  \    /  \ 
     *   /   \                            /    \  /    \ 
     *  LL   LR                                  LR
     * /  \ /  \                                /  \
     */

    LR=L->Right;
    Parent=Node->Parent;

    Node->Parent=L;
    L->Parent=Parent;
    if(LR!=NULL){
      LR->Parent=Node;
    }
    
    if(Parent==NULL){
      *Tree=H_TreeNode_To_H_TreeNode_AVL(L);
    }else{
      ReplaceChildNode(Parent,Node,L);
    }
    L->Right=Node;
    Node->Left=LR;

    //因子更正
    if(L_Factor==0){
      H_TreeNode_To_H_TreeNode_AVL(L)->Factor=1;
      H_TreeNode_To_H_TreeNode_AVL(Node)->Factor=-1;
      *LevelDecrease=0;
    }else{
      H_TreeNode_To_H_TreeNode_AVL(L)->Factor=0;
      H_TreeNode_To_H_TreeNode_AVL(Node)->Factor=0;
      *LevelDecrease=1;
    }

    Node=L;
  }

  return Node;
}

static inline H_TreeNode* adjustNode_R(H_TreeNode_AVL** Tree,H_TreeNode* Node,int* LevelDecrease){
  H_TreeNode* Parent;
  H_TreeNode* R;
  H_TreeNode* RL;
  int R_Factor;

  R=Node->Right;//此时R肯定存在
  R_Factor=H_TreeNode_To_H_TreeNode_AVL(R)->Factor;
  if(R_Factor<0){//RL最高
    int RL_Fact;
    H_TreeNode* RLR;
    H_TreeNode* RLL;
    //转换为RR最高

    RL=R->Left;//此时RL肯定存在
    RLR=RL->Right;
    RLL=RL->Left;
    Parent=Node->Parent;

    Node->Parent=RL;
    R->Parent=RL;
    RL->Parent=Parent;
    if(RLR!=NULL){
      RLR->Parent=R;
    }
    if(RLL!=NULL){
      RLL->Parent=Node;
    }

    if(Parent==NULL){
      *Tree=H_TreeNode_To_H_TreeNode_AVL(RL);
    }else{
      ReplaceChildNode(Parent,Node,RL);
    }
    Node->Right=RLL;
    R->Left=RLR;
    RL->Right=R;
    RL->Left=Node;

    //因子更正
    RL_Fact=H_TreeNode_To_H_TreeNode_AVL(RL)->Factor;
    if(RL_Fact==1){
      H_TreeNode_To_H_TreeNode_AVL(Node)->Factor=-1;
    }else{
      H_TreeNode_To_H_TreeNode_AVL(Node)->Factor=0;
    }
    if(RL_Fact==(-1)){
      H_TreeNode_To_H_TreeNode_AVL(R)->Factor=1;
    }else{
      H_TreeNode_To_H_TreeNode_AVL(R)->Factor=0;
    }
    H_TreeNode_To_H_TreeNode_AVL(RL)->Factor=0;

    *LevelDecrease=1;
    Node=RL;
  }else{
    //RR最高
    
    RL=R->Left;
    Parent=Node->Parent;

    Node->Parent=R;
    R->Parent=Parent;
    if(RL!=NULL){
      RL->Parent=Node;
    }
    
    if(Parent==NULL){
      *Tree=H_TreeNode_To_H_TreeNode_AVL(R);
    }else{
      ReplaceChildNode(Parent,Node,R);
    }
    R->Left=Node;
    Node->Right=RL;

    //因子更正
    if(R_Factor==0){
      H_TreeNode_To_H_TreeNode_AVL(R)->Factor=-1;
      H_TreeNode_To_H_TreeNode_AVL(Node)->Factor=1;
      *LevelDecrease=0;
    }else{
      H_TreeNode_To_H_TreeNode_AVL(R)->Factor=0;
      H_TreeNode_To_H_TreeNode_AVL(Node)->Factor=0;
      *LevelDecrease=1;
    }

    Node=R;
  }

  return Node;
}


static void treeFix_Insert(H_TreeNode_AVL** Tree,H_TreeNode* Node,H_TreeNode* SNode){

  while(Node!=NULL){
    int Factor;
    H_TreeNode* Parent;

    Factor=H_TreeNode_To_H_TreeNode_AVL(Node)->Factor;
    if(Node->Left==SNode){
      Factor-=1;
    }else{
      Factor+=1;
    }
    H_TreeNode_To_H_TreeNode_AVL(Node)->Factor=Factor;

    if(Factor==0){
      //新增节点后 树变为平衡 说明树高度肯定没有变化 不需要继续检查父节点
      return;
    }

    //新增节点后未平衡 树肯定增高

    if(Factor<(-1)){
      int LevelDecrease;
      Node=adjustNode_L(Tree,Node,&LevelDecrease);
      // if(LevelDecrease>0){
        //平衡后树变矮 抵消了前面增长的高度 父节点一定处于平衡状态
        return;
      // }
    }else if(Factor>1){
      int LevelDecrease;
      Node=adjustNode_R(Tree,Node,&LevelDecrease);
      // if(LevelDecrease>0){
        //平衡后树变矮 抵消了前面增长的高度 父节点一定处于平衡状态
        return;
      // }
    }

    Parent=Node->Parent;
    if(Parent==NULL){
      return;
    }
    SNode=Node;
    Node=Parent;
  }
}

static void treeFix_Remove(H_TreeNode_AVL** Tree,H_TreeNode* Node,int IsL){

  while(Node!=NULL){
    int Factor;
    int new_Factor;
    H_TreeNode* Parent;

    Factor=H_TreeNode_To_H_TreeNode_AVL(Node)->Factor;
    if(IsL!=0){
      new_Factor=Factor+1;
    }else{
      new_Factor=Factor-1;
    }
    H_TreeNode_To_H_TreeNode_AVL(Node)->Factor=new_Factor;

    if(Factor==0){
      //移除节点前 树是平衡的 说明树高度肯定没有变化 不需要继续检查父节点
      return;
    }

    //移除节点前未平衡 树变矮或者不变

    if(new_Factor<(-1)){
      int LevelDecrease;
      //因子差异变大 树高度肯定不变
      Node=adjustNode_L(Tree,Node,&LevelDecrease);
      if(LevelDecrease==0){
        //树高度不变
        return;
      }
      //平衡后树变矮
    }else if(new_Factor>1){
      int LevelDecrease;
      //因子差异变大 树高度肯定不变
      Node=adjustNode_R(Tree,Node,&LevelDecrease);
      if(LevelDecrease==0){
        //树高度不变
        return;
      }
      //平衡后树变矮
    }
    // else{ //new_Factor==0
    //   //这里不可能出现 new_Factor==-1或者new_Factor==1的情况，因为这需要Factor==0 然而前置逻辑以及排除掉了
    //   //树变矮
    // }

    Parent=Node->Parent;
    if(Parent==NULL){
      return;
    }
  
    //无论如何树都是变矮 继续向上检查
    if(Parent->Left==Node){
      IsL=1;
    }else{
      IsL=0;
    }
    Node=Parent;
  }
}




void H_Tree_AVL_InsertTo(H_TreeNode_AVL** Tree,H_TreeNode_AVL* Node,H_TreeNode_AVL* ReturnNode,int FindInsert_Result){

  Node->Node.Left=NULL;
  Node->Node.Right=NULL;
  Node->Factor=0;

  switch(FindInsert_Result){
    case vH_Tree_FindInsert_Result_InsertToLeft:
      ReturnNode->Node.Left=&Node->Node;
      Node->Node.Parent=&ReturnNode->Node;
      treeFix_Insert(Tree,&ReturnNode->Node,&Node->Node);
      break;
    case vH_Tree_FindInsert_Result_InsertToRight:
      ReturnNode->Node.Right=&Node->Node;
      Node->Node.Parent=&ReturnNode->Node;
      treeFix_Insert(Tree,&ReturnNode->Node,&Node->Node);
      break;
    case vH_Tree_FindInsert_Result_InsertToRoot:
      *Tree=Node;
      Node->Node.Parent=NULL;
      break;
    default:
      break;
  }

}

void H_Tree_AVL_Remove(H_TreeNode_AVL** Tree,H_TreeNode_AVL* Node){
  H_TreeNode* CurrentNode;
  H_TreeNode* Left;
  H_TreeNode* Right;

  CurrentNode=&Node->Node;
  Left=CurrentNode->Left;
  Right=CurrentNode->Right;
  if(Left!=NULL){
    if(Right!=NULL){// L:Left R:Right
      int IsL;

      IsL=RemoveNode_LR(Tree,&CurrentNode);//不要用RemoveNode_LR(Tree,&CurrentNode)代替下一行的IsL 因为这样做的话CurrentNode的取值与RemoveNode_LR的调用之间的顺序是未定义的
      treeFix_Remove(Tree,CurrentNode,IsL);
    }else{// L:Left R:NULL
      H_TreeNode* Parent;
      Parent=Node->Node.Parent;
      Left->Parent=Parent;
      if(Parent==NULL){
        *Tree=H_TreeNode_To_H_TreeNode_AVL(Left);
      }else{
        treeFix_Remove(Tree,Parent,ReplaceChildNode(Parent,CurrentNode,Left));
      }
    }
  }else{
    if(Right!=NULL){// L:NULL R:Right
      H_TreeNode* Parent;
      Parent=Node->Node.Parent;
      Right->Parent=Parent;
      if(Parent==NULL){
        *Tree=H_TreeNode_To_H_TreeNode_AVL(Right);
      }else{
        treeFix_Remove(Tree,Parent,ReplaceChildNode(Parent,CurrentNode,Right));
      }
    }else{// L:NULL R:NULL
      H_TreeNode* Parent;
      Parent=Node->Node.Parent;
      if(Parent==NULL){
        *Tree=NULL;
      }else{
        treeFix_Remove(Tree,Parent,ReplaceChildNode(Parent,CurrentNode,NULL));
      }
    }
  }
}



